<!DOCTYPE html>
<html lang='zh-CN'>

<head>
  <meta name="generator" content="Hexo 5.4.0">
  <meta charset="utf-8">
  

  <meta http-equiv='x-dns-prefetch-control' content='on' />
  <link rel='dns-prefetch' href='https://cdn.jsdelivr.net'>
  <link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin>
  <link href="https://cdn.bootcdn.net/ajax/libs/KaTeX/0.13.0/katex.min.css" rel="stylesheet">
	<script src="https://cdn.bootcdn.net/ajax/libs/KaTeX/0.13.0/katex.min.js"></script>
	<script>
    
		var katex_config = {
	  delimiters: 
	  [
		  {left: "$$", right: "$$", display: true},
  		{left: "$", right: "$", display: false}
	  ]
    };
    


	</script>
	<script defer src="https://cdn.bootcdn.net/ajax/libs/KaTeX/0.13.0/contrib/auto-render.min.js" onload="renderMathInElement(document.body,katex_config)"></script>

  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  <title>排序算法备忘录（二） - Debug Myself</title>

  

  
    <meta name="description" content="这是排序算法备忘录的第二篇。这一篇是关于插入排序。  插入排序 插入排序的原理类似于日常生活中排序的方法，先找到一个有序的数列，把一个数按照一定的顺序与有序数列中的数字进行比较，找到所在的位置，放入其中，构成一个新的有序列表。  代码实现 具体代码如下： 12345678910111213141516171819# 使用 random 中的 shuffle 生成一个乱序的数字序列import ra">
<meta property="og:type" content="article">
<meta property="og:title" content="排序算法备忘录（二）">
<meta property="og:url" content="https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/index.html">
<meta property="og:site_name" content="Debug Myself">
<meta property="og:description" content="这是排序算法备忘录的第二篇。这一篇是关于插入排序。  插入排序 插入排序的原理类似于日常生活中排序的方法，先找到一个有序的数列，把一个数按照一定的顺序与有序数列中的数字进行比较，找到所在的位置，放入其中，构成一个新的有序列表。  代码实现 具体代码如下： 12345678910111213141516171819# 使用 random 中的 shuffle 生成一个乱序的数字序列import ra">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/Position_Error_and_Count_Error_among_1000_Experiments.svg">
<meta property="og:image" content="https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/Position_Error_and_Count_Error_among_Different_Data_Sizes.svg">
<meta property="article:published_time" content="2021-04-16T16:53:19.000Z">
<meta property="article:modified_time" content="2021-04-17T11:14:33.810Z">
<meta property="article:author" content="Asante Stassenger">
<meta property="article:tag" content="Python">
<meta property="article:tag" content="Algorithm">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/Position_Error_and_Count_Error_among_1000_Experiments.svg">
  
  

  <!-- feed -->
  

  
    
<link rel="stylesheet" href="/css/main.css">

  

  
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --></head>

<body>
  


  <div class='l_body' id='start'>
    <aside class='l_left'>
    

<header class='header'>
  <div class='logo-wrap'>
  
  
    <a class='title' href='/'>
      Debug Myself
    </a>
  
</div>

  <nav class="menu dis-select"><a class="nav-item active" href="/">文章</a><a class="nav-item" href="/2021/08/09/about/">关于</a></nav>
</header>

<div class='widgets'>
  
    
      
      
<div class="widget-wrap" id="toc"><div class="widget-header h4 dis-select"><span class="name">本文目录</span></div><div class="widget-body fs14 post"><div class="doc-tree active"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="toc-text"> 插入排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-text"> 代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E5%9B%A0%E6%8E%A2%E7%A9%B6"><span class="toc-text"> 原因探究</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%90%86%E8%AE%BA%E5%88%86%E6%9E%90"><span class="toc-text"> 理论分析</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%9E%E9%99%85%E9%AA%8C%E8%AF%81"><span class="toc-text"> 实际验证</span></a></li></ol></li></ol></div></div></div>

    
  
</div>


    </aside>
    <div class='l_main'>
      

      


  <div class='bread-nav fs12'>
  
    
    <div id='breadcrumb'>
      <a class='cap breadcrumb' href='/'>主页</a>
      <span class="sep"></span>
      <a class='cap breadcrumb' href='/'>文章</a>
      
    </div>
    <div id='post-meta'>
      发布于&nbsp;<time datetime='2021-04-16T16:53:19.000Z'>2021-04-17</time>
    </div>
  
  </div>


<article class='content md post'>
<h1 class="article-title"><span>排序算法备忘录（二）</span></h1>
<p>这是排序算法备忘录的第二篇。这一篇是关于插入排序。</p>
<h2 id="插入排序"><a class="markdownIt-Anchor" href="# 插入排序"></a> 插入排序</h2>
<p>插入排序的原理类似于日常生活中排序的方法，先找到一个有序的数列，把一个数按照一定的顺序与有序数列中的数字进行比较，找到所在的位置，放入其中，构成一个新的有序列表。</p>
<h3 id="代码实现"><a class="markdownIt-Anchor" href="# 代码实现"></a> 代码实现</h3>
<p>具体代码如下：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 使用 random 中的 shuffle 生成一个乱序的数字序列</span></span><br><span class="line"><span class="keyword">import</span> random</span><br><span class="line">n = <span class="number">1000</span></span><br><span class="line">lst = []</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">    lst.append(i)</span><br><span class="line">random.shuffle(lst)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 算法主体部分</span></span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>, n):</span><br><span class="line">    j = i - <span class="number">1</span></span><br><span class="line">    current = lst[i]</span><br><span class="line">    <span class="keyword">while</span> j &gt;= <span class="number">0</span> <span class="keyword">and</span> lst[j] &gt; current:</span><br><span class="line">        lst[j + <span class="number">1</span>] = lst[j]</span><br><span class="line">        j -= <span class="number">1</span></span><br><span class="line">    lst[j + <span class="number">1</span>] = current</span><br><span class="line"></span><br><span class="line"><span class="comment"># 检验排序结果 </span></span><br><span class="line"><span class="built_in">print</span>(lst)</span><br></pre></td></tr></table></figure>
<p>在最初自己实现插入排序的过程中，我也写出了如下的代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>, n):</span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(i):</span><br><span class="line">        <span class="keyword">if</span> lst[i] &lt; lst[j]:</span><br><span class="line">            <span class="comment"># 这里从有序表前开始比较，找到插入的位置，交换内容；</span></span><br><span class="line">            <span class="comment"># 之后的循环里，相当于 lst[i]中的新值寻找插入的位置；</span></span><br><span class="line">            <span class="comment"># 实际上，之后的循环实现了首次插入后，插入位置之后数据的整体后移</span></span><br><span class="line">            lst[i], lst[j] = lst[j], lst[i]</span><br></pre></td></tr></table></figure>
<p>在当前条件下，这样的实现在速度上会慢两倍左右。</p>
<h3 id="原因探究"><a class="markdownIt-Anchor" href="# 原因探究"></a> 原因探究</h3>
<p>我认为主要有两个原因：</p>
<ol>
<li>
<p>我之前的写法循环次数是固定的，前一半循环用来寻找数据，后一半循环用来挪动位置，所以总的循环次数是</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext>count</mtext><mn>1</mn></msub><mo>=</mo><mfrac><mrow><mi>n</mi><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><mn>2</mn></mfrac></mrow><annotation encoding="application/x-tex">\text{count}_1 = \frac{n(n-1)}{2}
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.76508em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord text"><span class="mord">count</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.113em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.427em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">2</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">n</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span></span></p>
<p>这相当于最坏的情况。而第一种写法同时实现了插入位置的查找和位置的挪动，所以更加高效</p>
</li>
<li>
<p>由于插入的位置平均下来位于有序数列的中间，所以单从循环次数看，大约比第二种写法少了一半，这在数据量大时更加明显。而且，第二种写法挪动位置时需要进行交换操作，而第一种只是进行一次复制，这也是效率更高的原因</p>
</li>
</ol>
<h3 id="理论分析"><a class="markdownIt-Anchor" href="# 理论分析"></a> 理论分析</h3>
<p>对于插入排序，最好的情况下，循环次数是</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext>count</mtext><mn>2</mn></msub><mo>=</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\text{count}_2 = n-1
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.76508em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord text"><span class="mord">count</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span></span></p>
<p>所以平均的情况下</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mover accent="true"><mtext>count</mtext><mo stretchy="true">‾</mo></mover><mo>=</mo><mfrac><mrow><msup><mi>n</mi><mn>2</mn></msup><mo>+</mo><mi>n</mi><mo>−</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>≈</mo><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">\overline{\text{count}} = \frac{n^2+n-2}{4} \approx n^2
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.81508em;vertical-align:0em;"></span><span class="mord overline"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.81508em;"><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord text"><span class="mord">count</span></span></span></span><span style="top:-3.73508em;"><span class="pstrut" style="height:3em;"></span><span class="overline-line" style="border-bottom-width:0.04em;"></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.177108em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.491108em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8641079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641079999999999em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></span></p>
<p>从实验结果来看，当数据量较大时，循环结果比较接近平均情况下的循环次数。</p>
<p>而且，对于插入位置来说，由于在我的实验条件下，每次取到的随机数据的大小是均匀的，大小交错的，所以每次插入的位置要么靠前，要么靠后，平均结果是相当于插入在了中间的位置，在这种假设下，循环次数应该是</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext>count</mtext><mn>3</mn></msub><mo>=</mo><mfrac><mrow><msup><mi>n</mi><mn>2</mn></msup><mo>−</mo><mi>n</mi></mrow><mn>4</mn></mfrac><mo>≈</mo><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">\text{count}_3=\frac{n^2-n}{4} \approx n^2 
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.76508em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord text"><span class="mord">count</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.177108em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.491108em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord mathdefault">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8641079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641079999999999em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></span></p>
<p>当 n 足够大时，这与平均情况下的结果是十分接近的。所以平均情况相当于每次都插入中间位置。</p>
<h3 id="实际验证"><a class="markdownIt-Anchor" href="# 实际验证"></a> 实际验证</h3>
<p>以下是我用 1-1000 的随机数列进行实验的结果：</p>
<div class="tag-plugin image"><div class="image-bg"><img class="lazy" src="" data-src="Position_Error_and_Count_Error_among_1000_Experiments.svg" alt="这是 1000 次实验下对于数据容量为 1000 的插入位置与中间位置的偏差以及循环次数与平均情况的偏差"/><a class="image-download blur" style="opacity:0" href="Position_Error_and_Count_Error_among_1000_Experiments.svg"><svg class="icon" style="width: 1em; height: 1em;vertical-align: middle;fill: currentColor;overflow: hidden;" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="3734"><path d="M561.00682908 685.55838913a111.03077546 111.03077546 0 0 1-106.8895062 0L256.23182837 487.72885783a55.96309219 55.96309219 0 0 1 79.13181253-79.18777574L450.70357448 523.88101491V181.55477937a55.96309219 55.96309219 0 0 1 111.92618438 0v344.06109173l117.07478902-117.07478901a55.96309219 55.96309219 0 0 1 79.13181252 79.18777574zM282.81429711 797.1487951h447.70473912a55.96309219 55.96309219 0 0 1 0 111.92618438H282.81429711a55.96309219 55.96309219 0 0 1 0-111.92618438z" p-id="3735"></path></svg></a></div><div class="image-meta"><span class="image-caption center">这是 1000 次实验下对于数据容量为 1000 的插入位置与中间位置的偏差以及循环次数与平均情况的偏差</span></div></div>
<blockquote>
<p>Position error 平均值为 1.95%，Count error 平均值为 1.73%</p>
</blockquote>
<p>可以看到，误差集中在 0.005 到 0.025，即 0.5% 到 2.5%，说明在数据规模为 1000 时，由 Count error 可以看出，每次结果都比较接近平均情况，由 Position Error 可以看出，在平均的情况下，插入位置比较接近中间位置，这验证了之前的假设。</p>
<div class="tag-plugin image"><div class="image-bg"><img class="lazy" src="" data-src="Position_Error_and_Count_Error_among_Different_Data_Sizes.svg" alt="这是不同数据规模下插入位置与中间位置的偏差和循环次数与平均情况的偏差 (每种规模 50 次实验)"/><a class="image-download blur" style="opacity:0" href="Position_Error_and_Count_Error_among_Different_Data_Sizes.svg"><svg class="icon" style="width: 1em; height: 1em;vertical-align: middle;fill: currentColor;overflow: hidden;" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="3734"><path d="M561.00682908 685.55838913a111.03077546 111.03077546 0 0 1-106.8895062 0L256.23182837 487.72885783a55.96309219 55.96309219 0 0 1 79.13181253-79.18777574L450.70357448 523.88101491V181.55477937a55.96309219 55.96309219 0 0 1 111.92618438 0v344.06109173l117.07478902-117.07478901a55.96309219 55.96309219 0 0 1 79.13181252 79.18777574zM282.81429711 797.1487951h447.70473912a55.96309219 55.96309219 0 0 1 0 111.92618438H282.81429711a55.96309219 55.96309219 0 0 1 0-111.92618438z" p-id="3735"></path></svg></a></div><div class="image-meta"><span class="image-caption center"> 这是不同数据规模下插入位置与中间位置的偏差和循环次数与平均情况的偏差(每种规模 50 次实验)</span></div></div>
<p>从这张图可以看到，当数据规模逐渐变大时，这种平均情况更加显著。</p>
<p>以下是进行测试的代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insertion</span>(<span class="params">n</span>):</span></span><br><span class="line">    lst = []</span><br><span class="line">    lst1 = []</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        lst1.append(i)</span><br><span class="line">    random.shuffle(lst1)</span><br><span class="line"></span><br><span class="line">    count = <span class="number">0</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>, n):</span><br><span class="line">        j = i - <span class="number">1</span></span><br><span class="line">        current = lst1[i]</span><br><span class="line">        <span class="keyword">while</span> j &gt;= <span class="number">0</span> <span class="keyword">and</span> lst1[j] &gt; current:</span><br><span class="line">            lst1[j + <span class="number">1</span>] = lst1[j]</span><br><span class="line">            j -= <span class="number">1</span></span><br><span class="line">            count += <span class="number">1</span></span><br><span class="line">        lst1[j + <span class="number">1</span>] = current</span><br><span class="line">        lst.append(j / i)</span><br><span class="line"></span><br><span class="line">    position = <span class="built_in">sum</span>(lst) / (n - <span class="number">1</span>)</span><br><span class="line">    position_err = <span class="built_in">abs</span>(position - <span class="number">0.5</span>) / <span class="number">0.5</span></span><br><span class="line">    half_count = n * (n - <span class="number">1</span>) / <span class="number">4</span> + n / <span class="number">2</span> - <span class="number">1</span> / <span class="number">2</span></span><br><span class="line">    count_err = <span class="built_in">abs</span>(count - half_count) / half_count</span><br><span class="line">    <span class="keyword">return</span> &#123;<span class="string">&#x27;position&#x27;</span>:position_err,<span class="string">&#x27;count&#x27;</span>:count_err&#125;</span><br><span class="line"></span><br><span class="line">pos = []</span><br><span class="line">counts = []</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1000</span>):</span><br><span class="line">    res = insertion(<span class="number">1000</span>)</span><br><span class="line">    position = res[<span class="string">&#x27;position&#x27;</span>]</span><br><span class="line">    count = res[<span class="string">&#x27;count&#x27;</span>]</span><br><span class="line">    pos.append(position)</span><br><span class="line">    counts.append(count)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&#x27;[<span class="subst">&#123;i&#125;</span>]:position error is <span class="subst">&#123;position:<span class="number">.2</span>%&#125;</span>, count error is <span class="subst">&#123;count:<span class="number">.2</span>%&#125;</span>&#x27;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&#x27;Position error in average is <span class="subst">&#123;<span class="built_in">sum</span>(pos) / <span class="built_in">len</span>(pos):<span class="number">.2</span>%&#125;</span>, count error in average is <span class="subst">&#123;<span class="built_in">sum</span>(counts) / <span class="built_in">len</span>(counts):<span class="number">.2</span>%&#125;</span>&#x27;</span>)</span><br><span class="line"></span><br><span class="line">aver_pos = []</span><br><span class="line">aver_count = []</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> (<span class="number">10</span>, <span class="number">50</span>, <span class="number">100</span>, <span class="number">500</span>, <span class="number">1000</span>, <span class="number">5000</span>):</span><br><span class="line">    pos_ = []</span><br><span class="line">    counts_ = []</span><br><span class="line">    <span class="keyword">for</span> _ <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">50</span>):</span><br><span class="line">        res = insertion(i)</span><br><span class="line">        position = res[<span class="string">&#x27;position&#x27;</span>]</span><br><span class="line">        count = res[<span class="string">&#x27;count&#x27;</span>]</span><br><span class="line">        pos_.append(position)</span><br><span class="line">        counts_.append(count)</span><br><span class="line">    aver_pos.append(<span class="built_in">sum</span>(pos_) / <span class="built_in">len</span>(pos_))</span><br><span class="line">    aver_count.append(<span class="built_in">sum</span>(counts_) / <span class="built_in">len</span>(counts_))</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">6</span>):    </span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&#x27;Data size:<span class="subst">&#123;i&#125;</span>, position error is <span class="subst">&#123;aver_pos[i]:<span class="number">.2</span>%&#125;</span>, count error is <span class="subst">&#123;aver_count[i]:<span class="number">.2</span>%&#125;</span>&#x27;</span>)</span><br><span class="line"></span><br><span class="line">x1 = <span class="built_in">range</span>(<span class="number">1000</span>)</span><br><span class="line">x2 = <span class="built_in">range</span>(<span class="number">1000</span>)</span><br><span class="line">x3 = <span class="built_in">range</span>(<span class="number">6</span>)</span><br><span class="line">plt.plot(x1, pos, label = <span class="string">&#x27;Position error&#x27;</span>, marker = <span class="string">&#x27;o&#x27;</span>)</span><br><span class="line">plt.plot(x2, counts, label = <span class="string">&#x27;Count error&#x27;</span>, marker = <span class="string">&#x27;x&#x27;</span>)</span><br><span class="line">plt.xlabel(<span class="string">&#x27;Experiment&#x27;</span>)</span><br><span class="line">plt.ylabel(<span class="string">&#x27;Error&#x27;</span>)</span><br><span class="line">plt.title(<span class="string">&#x27;Position Error and Count Error among 1000 Experiments&#x27;</span>)</span><br><span class="line">plt.legend()</span><br><span class="line">plt.show()</span><br><span class="line"></span><br><span class="line">plt.plot(x3, aver_pos, label = <span class="string">&#x27;Position error&#x27;</span>, marker = <span class="string">&#x27;o&#x27;</span>)</span><br><span class="line">plt.plot(x3, aver_count, label = <span class="string">&#x27;Count error&#x27;</span>, marker = <span class="string">&#x27;x&#x27;</span>)</span><br><span class="line">plt.xlabel(<span class="string">&#x27;Experiment&#x27;</span>)</span><br><span class="line">plt.xticks(x3, [<span class="string">&#x27;10&#x27;</span>, <span class="string">&#x27;50&#x27;</span>, <span class="string">&#x27;100&#x27;</span>, <span class="string">&#x27;500&#x27;</span>, <span class="string">&#x27;1000&#x27;</span>, <span class="string">&#x27;5000&#x27;</span>, ])</span><br><span class="line">plt.ylabel(<span class="string">&#x27;Error&#x27;</span>)</span><br><span class="line">plt.title(<span class="string">&#x27;Position Error and Count Error among Different Data Sizes&#x27;</span>)</span><br><span class="line">plt.legend()</span><br><span class="line">plt.show()</span><br></pre></td></tr></table></figure>


<div class="article-footer fs14"><section id="license"><div class="header"><span>许可协议</span></div><div class="body"><p>本文采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">署名-非商业性使用-相同方式共享 4.0 国际</a> 许可协议，转载请注明出处。</p>
</div></section><section id="share"><div class="header"><span>分享文章</span></div><div class="body"><div class="link"><input class="copy-area" readonly="true" id="copy-link" value="https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/" /></div><div class="social-wrap dis-select"><a class="social share-item wechat" onclick="util.toggle(&quot;qrcode-wechat&quot)"><img class="lazy" src="" data-src="https://cdn.jsdelivr.net/gh/cdn-x/placeholder@1.0.1/social/b32ef3da1162a.svg"/></a><a class="social share-item email" href="mailto:?subject=排序算法备忘录（二） - Debug Myself&amp;body=https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/"><img class="lazy" src="" data-src="https://cdn.jsdelivr.net/gh/cdn-x/placeholder@1.0.1/social/a1b00e20f425d.svg"/></a><a class="social share-item link" onclick="util.copy(&quot;copy-link&quot;, &quot;复制成功&quot;)"><img class="lazy" src="" data-src="https://cdn.jsdelivr.net/gh/cdn-x/placeholder@1.0.1/social/8411ed322ced6.svg"/></a></div><div class="qrcode" id="qrcode-wechat" style="visibility:hidden;height:0"><img class="lazy" src="" data-src="https://api.qrserver.com/v1/create-qr-code/?size=256x256&data=https://stassenger.gitee.io/2021/04/17/sort-algorithm-reminder-2/index.html"/></div></div></section></div>

</article>

<div class="related-wrap" id="read-next"><section class="header cap theme"><span>接下来阅读</span></section><section class="body"><div class="post-title h2"><a href="/2021/04/15/sort_algorithm_reminder_1/">排序算法备忘录（一）</a></div><div class="post-title fs14"><a href="/2021/06/12/a%20problem%20when%20adding%20NJU%20email%20to%20Window%2010%20mail%20app/">上一篇：关于在 Windows10 自带的邮件应用中添加南大邮箱遇到的问题</a></div></section></div>






  <div class='related-wrap md' id="comments">
    <div class='cmt-title cap theme'>
      快来参与讨论吧
    </div>
    <div class='cmt-body valine'>
      

<div id="valine_container" class="valine_thread"><svg class="loading" style="vertical-align: middle;fill: currentColor;overflow: hidden;" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="2709"><path d="M832 512c0-176-144-320-320-320V128c211.2 0 384 172.8 384 384h-64zM192 512c0 176 144 320 320 320v64C300.8 896 128 723.2 128 512h64z" p-id="2710"></path></svg></div>

    </div>
  </div>



      
<footer class="page-footer fs12"><hr><div><p>本博客所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a> 许可协议，转载请注明出处。</p>
<p>本站由 <a href="https://stassenger.gitee.io/">@Asante Stassenger</a> 创建，使用 <a target="_blank" rel="noopener" href="https://github.com/xaoxuu/hexo-theme-stellar/tree/1.1.0">Stellar</a> 作为主题。</p>
</div></footer>


      <div class='float-panel mobile-only' style='display:none'>
  <button type='button' class='sidebar-toggle mobile' onclick='sidebar.toggle()'>
    <svg class="icon" viewBox="0 0 1228 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="2849"><path d="M0 0m97.390199 0l973.901995 0q97.390199 0 97.390199 97.390199l0 0q0 97.390199-97.390199 97.3902l-973.901995 0q-97.390199 0-97.390199-97.3902l0 0q0-97.390199 97.390199-97.390199Z" p-id="2850"></path><path d="M0 389.560798m97.390199 0l973.901995 0q97.390199 0 97.390199 97.390199l0 0q0 97.390199-97.390199 97.3902l-973.901995 0q-97.390199 0-97.390199-97.3902l0 0q0-97.390199 97.390199-97.390199Z" p-id="2851"></path><path d="M0 779.121596m97.390199 0l973.901995 0q97.390199 0 97.390199 97.390199l0 0q0 97.390199-97.390199 97.390199l-973.901995 0q-97.390199 0-97.390199-97.390199l0 0q0-97.390199 97.390199-97.390199Z" p-id="2852"></path></svg>
  </button>
</div>

    </div>
  </div>
  <div class='scripts'>
    <script type="text/javascript">
  stellar = {
    // 懒加载 css https://github.com/filamentgroup/loadCSS
    loadCSS: (href, before, media, attributes) => {
      var doc = window.document;
      var ss = doc.createElement("link");
      var ref;
      if (before) {
        ref = before;
      } else {
        var refs = (doc.body || doc.getElementsByTagName("head")[0]).childNodes;
        ref = refs[refs.length - 1];
      }
      var sheets = doc.styleSheets;
      if (attributes) {
        for (var attributeName in attributes) {
          if (attributes.hasOwnProperty(attributeName)) {
            ss.setAttribute(attributeName, attributes[attributeName]);
          }
        }
      }
      ss.rel = "stylesheet";
      ss.href = href;
      ss.media = "only x";
      function ready(cb) {
        if (doc.body) {
          return cb();
        }
        setTimeout(function () {
          ready(cb);
        });
      }
      ready(function () {
        ref.parentNode.insertBefore(ss, before ? ref : ref.nextSibling);
      });
      var onloadcssdefined = function (cb) {
        var resolvedHref = ss.href;
        var i = sheets.length;
        while (i--) {
          if (sheets[i].href === resolvedHref) {
            return cb();
          }
        }
        setTimeout(function () {
          onloadcssdefined(cb);
        });
      };
      function loadCB() {
        if (ss.addEventListener) {
          ss.removeEventListener("load", loadCB);
        }
        ss.media = media || "all";
      }
      if (ss.addEventListener) {
        ss.addEventListener("load", loadCB);
      }
      ss.onloadcssdefined = onloadcssdefined;
      onloadcssdefined(loadCB);
      return ss;
    },

    // 从 butterfly 和 volantis 获得灵感
    loadScript: (src, opt) => new Promise((resolve, reject) => {
      var script = document.createElement('script')
      script.src = src
      if (opt) {
        for (let key of Object.keys(opt)) {
          script[key] = opt[key]
        }
      } else {
        // 默认异步，如果需要同步，第二个参数传入 {} 即可
        script.async = true
      }
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    }),

    // https://github.com/jerryc127/hexo-theme-butterfly
    jQuery: (fn) => {
      if (typeof jQuery === 'undefined') {
        stellar.loadScript(stellar.plugins.jQuery).then(fn)
      } else {
        fn()
      }
    }
  };
  stellar.github = 'https://github.com/xaoxuu/hexo-theme-stellar/tree/1.1.0';
  stellar.config = {
    date_suffix: {
      just: '刚刚',
      min: '分钟前',
      hour: '小时前',
      day: '天前',
      month: '个月前',
    },
  };

  // required plugins (only load if needs)
  stellar.plugins = {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js',
    sitesjs: '/js/plugins/sites.js',
    friendsjs: '/js/plugins/friends.js',
  };

  // optional plugins
  if ('true' == 'true') {
    stellar.plugins.lazyload = Object.assign({"enable":true,"js":"https://cdn.jsdelivr.net/npm/vanilla-lazyload@17.3.1/dist/lazyload.min.js","transition":"blur"});
  }
  if ('true' == 'true') {
    stellar.plugins.swiper = Object.assign({"enable":true,"css":"https://unpkg.com/swiper/swiper-bundle.min.css","js":"https://unpkg.com/swiper/swiper-bundle.min.js"});
  }
  if ('' == 'true') {
    stellar.plugins.scrollreveal = Object.assign({"enable":null,"js":"https://cdn.jsdelivr.net/npm/scrollreveal@4.0.9/dist/scrollreveal.min.js","distance":"8px","duration":500,"interval":100,"scale":1});
  }
  if ('true' == 'true') {
    stellar.plugins.preload = Object.assign({"enable":true,"service":"flying_pages","instant_page":"https://cdn.jsdelivr.net/gh/volantis-x/cdn-volantis@4.1.2/js/instant_page.js","flying_pages":"https://cdn.jsdelivr.net/gh/gijo-varghese/flying-pages@2.1.2/flying-pages.min.js"});
  }
</script>

<!-- required -->

  
<script src="/js/main.js" async></script>



<!-- optional -->

  <script>
  function getEmojiMaps() {
    function emoji(path, idx, ext) {
      return path + "/" + path + "-" + idx + "." + ext;
    }
    var emojiMaps = {};
    for (var i = 1; i <= 54; i++) {
      emojiMaps['tieba-' + i] = emoji('tieba', i, 'png');
    }
    for (var i = 1; i <= 101; i++) {
      emojiMaps['qq-' + i] = emoji('qq', i, 'gif');
    }
    for (var i = 1; i <= 116; i++) {
      emojiMaps['aru-' + i] = emoji('aru', i, 'gif');
    }
    for (var i = 1; i <= 125; i++) {
      emojiMaps['twemoji-' + i] = emoji('twemoji', i, 'png');
    }
    for (var i = 1; i <= 4; i++) {
      emojiMaps['weibo-' + i] = emoji('weibo', i, 'png');
    }
    return emojiMaps;
  }
  function load_comment(){
    if(!document.getElementById("valine_container"))return;
    stellar.loadScript('https://cdn.jsdelivr.net/gh/XuxuGood/simple-blog-cdn@main/js/Valine.min.js', {defer:true}).then(function () {
      const el = document.getElementById("valine_container");
      var path = el.getAttribute('comment_id');
      const placeholder = "";
      if (!path) {
        path = decodeURI(window.location.pathname);
      }
      var valine = new Valine();
      valine.init(Object.assign({"js":"https://cdn.jsdelivr.net/gh/XuxuGood/simple-blog-cdn@main/js/Valine.min.js","appId":"Gmd8dpj69RW0YYzTOgchjKDG-9Nh9j0Va","appKey":"8XTx3FrEGvL5fwadDKGc0sHf","placeholder":null,"visitor":true,"requiredFields":["nick","mail"],"enableQQ":true,"recordIP":false,"avatar":"robohash","pageSize":10,"lang":"zh-cn","highlight":true,"mathJax":false,"tagMeta":["博主","小伙伴","访客"],"metaPlaceholder":{"nick":"昵称/QQ号(必填)","mail":"邮箱（必填）"},"master":["6783037F2DF30EAB99F9FC256157D875"],"friends":["6783037F2DF30EAB99F9FC256157D875"]}, {
        el: '#valine_container',
        path: path,
        placeholder: placeholder,
        emojiCDN: 'https://cdn.jsdelivr.net/gh/volantis-x/cdn-emoji/valine/',
        emojiMaps: getEmojiMaps(),
      }));
    });
  }
  window.addEventListener('DOMContentLoaded', (event) => {
    console.log('DOM fully loaded and parsed');
    load_comment();
  });

</script>




<!-- inject -->


  </div>
</body>
</html>
